// https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/

// 算法思路总结：
// 1. 快速选择算法寻找前cnt个最小元素（部分排序）
// 2. 三路分区处理重复元素：<key, =key, >key
// 3. 根据cnt与分区大小的关系选择性递归
// 4. 边界处理：空数组或cnt=0时直接返回
// 5. 时间复杂度：O(n)，空间复杂度：O(logn)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

class Solution 
{
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        if (stock.empty() || cnt == 0) return {};
        
        srand((unsigned)time(NULL));
        qsort(stock, 0, stock.size() - 1, cnt);
        return {stock.begin(), stock.begin() + cnt};
    }

    int getRandom(vector<int>& stock, int left, int right)
    {
        int r = rand();
        return stock[r % (right - left + 1) + left];
    }

    void qsort(vector<int>& stock, int left, int right, int cnt)
    {
        if (left >= right || cnt == 0)
            return ;

        int key = getRandom(stock, left, right);
        int begin = left - 1, end = right + 1, cur = left;
        while (cur < end)
        {
            if (stock[cur] < key)
            {
                swap(stock[++begin], stock[cur++]);
            }
            else if (stock[cur] == key)
            {
                cur++;
            }
            else if (stock[cur] > key)
            {
                swap(stock[--end], stock[cur]);
            }
        }

        int a = begin - left + 1, b = end - begin - 1, c = right - end + 1;
        if (cnt <= a) qsort(stock, left, begin, cnt);
        else if (cnt <= a + b) return ;
        else qsort(stock, end, right, cnt - a - b);
    }
};

int main()
{
    vector<int> nums1 = {2,5,7,4}, nums2 = {0,2,3,6};
    int cnt1 = 1, cnt2 = 2;

    Solution sol;

    auto v1 = sol.inventoryManagement(nums1, cnt1);
    auto v2 = sol.inventoryManagement(nums2, cnt2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}